package com.leetcodehot.problems;

import java.util.ArrayList;
import java.util.List;

public class problems1110 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private int[] count;
    List<TreeNode> res;

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        res = new ArrayList<TreeNode>();
        count = new int[1001];
        for (int val : to_delete) {
            count[val] = 1;
        }
        dfs(root, to_delete, null);
        return res;
    }

    private void dfs(TreeNode root, int[] toDelete, TreeNode prenode) {
        if (root == null) return;
        if (prenode == null && count[root.val] == 0) {
            res.add(root);
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (count[root.val] == 1) {
            if (prenode != null) {
                if (prenode.left == root) {
                    prenode.left = null;
                } else {
                    prenode.right = null;
                }
            }
            dfs(left, toDelete, null);
            dfs(right, toDelete, null);
        } else {
            dfs(left, toDelete, root);
            dfs(right, toDelete, root);
        }
    }
}
